#include<stdio.h>
#include<stdlib.h>
#define MaxVertexNum 100
#define INFINITY 99999
#define ERROR -1
typedef int Vertex;
typedef int WeightType;
typedef struct ENode *PtrToENode;
struct ENode
{
    int id;
    Vertex V1, V2;
    WeightType Weight;
};
typedef PtrToENode Edge;
struct ENode edgelist[MaxVertexNum];
int MST[MaxVertexNum] = {0};

typedef struct gNode *PtrToGNode;
struct gNode
{
    int Nv;
    int Ne;
    WeightType G[MaxVertexNum][MaxVertexNum];
};
typedef PtrToGNode MGraph;

Vertex FindMinDist(MGraph Graph, WeightType dist[])
{
    Vertex MinV, V;
    WeightType MinDist = INFINITY;
 
    for(V=0; V<Graph->Nv; V++) 
    {
        if(dist[V]!=0 && dist[V]<MinDist) 
        {   
            MinDist = dist[V];
            MinV = V;
        }
    }
    if(MinDist < INFINITY)
        return MinV;
    else return ERROR;
}
 
int Prim(MGraph Graph, int MST[])
{ /* 将最小生成树保存到数组MST，返回最小权重和 */
    WeightType dist[MaxVertexNum], TotalWeight;
    Vertex parent[MaxVertexNum], V, W;
    int VCount;
    Edge E;    
    for(V=0; V<Graph->Nv; V++) 
    {   
        dist[V] = Graph->G[0][V];
        parent[V] = 0; /* 暂且定义所有顶点的父结点都是初始点0 */ 
    }
    TotalWeight = 0;
    VCount = 0;      /* 初始化收录的顶点数 */
    E = (Edge)malloc(sizeof(struct ENode));
    int ECNT = 0;
    /* 将初始点0收录进MST */
    dist[0] = 0;
    VCount++;
    parent[0] = -1; /* 当前树根是0 */
    while(1) 
    {
        V = FindMinDist(Graph, dist);
        /* V = 未被收录顶点中dist最小者 */
        if (V == ERROR)
            break;            
        /* 将V及相应的边<parent[V], V>收录进MST */
        E->V1 = parent[V];
        E->V2 = V;
        E->Weight = dist[V];
        E->id = FindEdge(E->V1, E->V2);
        if(E->id!=ERROR) MST[ECNT++] = E->id;
        TotalWeight += dist[V];
        dist[V] = 0;
        VCount++;
        for(W=0; W<Graph->Nv; W++) /* 对图中的每个顶点W */
            if(dist[W]!=0 && Graph->G[V][W]<INFINITY) 
            {/* 若W是V的邻接点并且未被收录 */           
                if(Graph->G[V][W] < dist[W]) 
                {/* 若收录V使得dist[W]变小 */               
                    dist[W] = Graph->G[V][W]; /* 更新dist[W] */
                    parent[W] = V; /* 更新树 */
                }
            }
    } /* while结束*/
    if(VCount < Graph->Nv) /* MST中收的顶点不到|V|个 */
       TotalWeight = ERROR;
    printf("%d\n", TotalWeight);
    return ECNT;
}

MGraph CreateGraph(int VertexNum)
{
    Vertex V, W;
    MGraph Graph;
    Graph = (MGraph)malloc(sizeof(struct gNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    for (V=0; V<Graph->Nv; V++)
        for (W=0; W<Graph->Nv; W++)
            Graph->G[V][W] = INFINITY;
    return Graph;
}
        
void Insertedge(MGraph Graph, Edge E)
{
    Graph->G[E->V1][E->V2] = E->Weight;    
    Graph->G[E->V2][E->V1] = E->Weight;
}
 
MGraph BuildGraph()
{
    MGraph Graph;
    Edge E;
    int Nv, i;    
    scanf("%d", &Nv);
    Graph = CreateGraph(Nv);
    scanf("%d", &(Graph->Ne));
    if (Graph->Ne != 0) 
    {
        E = (Edge)malloc(sizeof(struct ENode));
        for (i=0; i<Graph->Ne; i++) 
        {
            scanf("%d %d %d %d", &E->id, &E->V1, &E->V2, &E->Weight);
            edgelist[i].id = E->id;
            edgelist[i].V1 = E->V1;
            edgelist[i].V2 = E->V2;
            Insertedge(Graph, E);
        }
    }
    return Graph;
}

int cmp(const void *a, const void *b)
{
    return (*(int *)a > *(int *)b);
}

int FindEdge(Vertex V1, Vertex V2)
{
    int id = ERROR;
    for(int i=0;i<MaxVertexNum;i++)
    {
        if(edgelist[i].V1 == V1 && edgelist[i].V2 == V2)
        {
            id = edgelist[i].id;
            break;
        }
        else if(edgelist[i].V1 == V2 && edgelist[i].V2 == V1)
        {
            id = edgelist[i].id;
            break;
        }
    }
    return id;
}

int main()
{
    for(int i=0;i<MaxVertexNum;i++)
    {
        edgelist[i].id = ERROR;
        edgelist[i].V1 = edgelist[i].V2 = -1;
    } 
    MGraph G = BuildGraph();
    int cnt = Prim(G, MST);
    qsort(MST, cnt, sizeof(int), cmp);
    for(int i=0;i<cnt;i++)
        printf("%d ", MST[i]);
    return 0;
}